package leetcode;

import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-04 13:45
 **/
public class LeetCode913 {

    /*static final int MOUSE_WIN = 1;
    static final int CAT_WIN = 2;
    static final int DRAW = 0;
    int n;
    int[][] graph;
    int[][][] dp;

    public int catMouseGame(int[][] graph) {
        this.n = graph.length;
        this.graph = graph;
        this.dp = new int[n][n][n * 2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        return getResult(1, 2, 0);
    }

    public int getResult(int mouse, int cat, int turns) {
        if (turns == n * 2) {
            return DRAW;
        }
        if (dp[mouse][cat][turns] < 0) {
            if (mouse == 0) {
                dp[mouse][cat][turns] = MOUSE_WIN;
            } else if (cat == mouse) {
                dp[mouse][cat][turns] = CAT_WIN;
            } else {
                getNextResult(mouse, cat, turns);
            }
        }
        return dp[mouse][cat][turns];
    }

    public void getNextResult(int mouse, int cat, int turns) {
        int curMove = turns % 2 == 0 ? mouse : cat;
        int defaultResult = curMove == mouse ? CAT_WIN : MOUSE_WIN;
        int result = defaultResult;
        int[] nextNodes = graph[curMove];
        for (int next : nextNodes) {
            //如果当前是猫移动,且移动的位置是0,那么跳过当前轮,即猫不能移动到0(洞)
            if (curMove == cat && next == 0) {
                continue;
            }
            //如果是老鼠的回合,老鼠移动到next
            int nextMouse = curMove == mouse ? next : mouse;
            //如果是猫的回合,猫移动到next
            int nextCat = curMove == cat ? next : cat;
            int nextResult = getResult(nextMouse, nextCat, turns + 1);
            if (nextResult != defaultResult) {
                result = nextResult;
                if (result != DRAW) {
                    break;
                }
            }
        }
        dp[mouse][cat][turns] = result;
    }*/

    /**
     * 平局
     */
    private static final int DRAW = 0;
    /**
     * 老鼠赢
     */
    private static final int MOUSE_WIN = 1;
    /**
     * 猫赢
     */
    private static final int CAT_WIN = 2;

    /*public int catMouseGame(int[][] graph) {
        int n = graph.length;
        int[][][] memo = new int[n][n][2 * n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(memo[i][j], -1);
            }
        }
        return dfs(graph, n, memo, 2, 1, 0);
    }

    private int dfs(int[][] graph, int n, int[][][] memo, int catPos, int mousePos, int turns) {
        // 超过节点数两倍，可以确定为平局
        if (turns == 2 * n) {
            return 0;
        }

        // 缓存中有，直接返回
        if (memo[catPos][mousePos][turns] != -1) {
            return memo[catPos][mousePos][turns];
        }

        // 老鼠赢
        if (mousePos == 0) {
            return memo[catPos][mousePos][turns] = MOUSE_WIN;
        }

        // 猫赢
        if (catPos == mousePos) {
            return memo[catPos][mousePos][turns] = CAT_WIN;
        }

        // turns 为偶数是轮到老鼠走，为奇数是轮到猫走
        if (turns % 2 == 0) {
            // 老鼠最坏情况是猫赢
            int ans = CAT_WIN;
            // 尝试走到下一个节点
            for (int nextPos : graph[mousePos]) {
                int nextAns = dfs(graph, n, memo, catPos, nextPos, turns + 1);
                // 如果老鼠可以赢，直接返回
                if (nextAns == MOUSE_WIN) {
                    return memo[catPos][mousePos][turns] = MOUSE_WIN;
                }
                // 有平局，先记录为平局，后面如果有老鼠可以赢的场景，通过上述语句可以返回
                if (nextAns == DRAW) {
                    ans = DRAW;
                }
            }
            // 返回老鼠走的结果,这里的结果只可能是平局或者必输,因为要是赢的情况上面就会返回了
            return memo[catPos][mousePos][turns] = ans;
        } else {
            // 猫最坏情况是老鼠赢
            int ans = MOUSE_WIN;
            for (int nextPos : graph[catPos]) {
                // 注意猫不能走到0号节点
                if (nextPos != 0) {
                    // 尝试进入下一个节点
                    int nextAns = dfs(graph, n, memo, nextPos, mousePos, turns + 1);
                    // 如果猫可以赢，直接返回
                    if (nextAns == CAT_WIN) {
                        return memo[catPos][mousePos][turns] = CAT_WIN;
                    }
                    // 有平局，先记录为平局，后面如果有猫可以赢的场景，通过上述语句可以返回
                    if (nextAns == DRAW) {
                        ans = DRAW;
                    }
                }
            }
            // 返回猫走的结果,这里的结果只可能是平局或者必输,因为要是赢的情况上面就会返回了
            return memo[catPos][mousePos][turns] = ans;
        }
    }*/

    public int catMouseGame(int[][] graph) {
        int n = graph.length;
        //dp数组用来记录老鼠和猫移动的每个位置的结果,记忆化搜索
        int[][][] dp = new int[n][n][2 * n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                Arrays.fill(dp[i][j], -1);
            }
        }

        return dfs(graph, dp, 1, 2, 0);
    }

    /**
     * 遍历的并记录当前位置猫或老鼠移动的最好的结果
     * @param graph
     * @param dp
     * @param mouse 老鼠当前位置
     * @param cat 猫当前位置
     * @param turns 回合
     * @return
     */
    int dfs(int[][] graph, int[][][] dp, int mouse, int cat, int turns) {
        //如果turns=2n,说明至少有一个点被重复遍历,直接返回平局
        if (turns == 2 * graph.length) {
            return DRAW;
        }

        //该位置曾经遍历过,直接返回结果
        if (dp[mouse][cat][turns] != -1) {
            return dp[mouse][cat][turns];
        }

        //如果mouse移动到0,鼠赢
        if (mouse == 0) {
            return dp[mouse][cat][turns] = MOUSE_WIN;
        }

        //如果cat移动到和老鼠一样的位置,猫赢
        if (cat == mouse) {
            return dp[mouse][cat][turns] = CAT_WIN;
        }

        //turns为偶数,老鼠的回合,否则猫的回合
        if ((turns & 1) != 1) {
            //最坏的情况是猫赢
            int ans = CAT_WIN;

            //遍历老鼠可以移动所有位置
            for (int next : graph[mouse]) {
                int nextResult = dfs(graph, dp, next, cat, turns + 1);

                //如果当前位置,老鼠可以赢,直接返回结果
                if (nextResult == MOUSE_WIN) {
                    return dp[mouse][cat][turns] = nextResult;
                }

                //有平局就记为平局,看下后面是否有更好的结果
                if (nextResult == DRAW) {
                    ans = nextResult;
                }
            }

            //返回老鼠赢不了的最好结果
            return dp[mouse][cat][turns] = ans;
        } else {
            //最坏的情况是老输赢
            int ans = MOUSE_WIN;

            //遍历猫可以移动的所有位置
            for (int next : graph[cat]) {
                //猫不能进洞(0)
                if (next == 0) {
                    continue;
                }

                int nextResult = dfs(graph, dp, mouse, next, turns + 1);

                //如果当前位置,猫可以赢,直接返回结果
                if (nextResult == CAT_WIN) {
                    return dp[mouse][cat][turns] = nextResult;
                }

                //有平局就记为平局,看下后面是否有更好的结果
                if (nextResult == DRAW) {
                    ans = nextResult;
                }
            }

            //返回猫赢不了的最好结果
            return dp[mouse][cat][turns] = ans;
        }
    }
    public static void main(String[] args) {
        LeetCode913 code = new LeetCode913();
        System.out.println(code.catMouseGame(new int[][]{{2, 5}, {3}, {0, 4, 5}, {1, 4, 5}, {2, 3}, {0, 2, 3}}));
    }

}
